package com.nowcoder.topic.dfs.middle;

import java.util.LinkedList;
import java.util.Queue;

/**
 * NC198 判断是不是完全二叉树
 * @author d3y1
 */
public class NC198{
    private int seq = 0;

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 程序入口
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    public boolean isCompleteTree (TreeNode root) {
        return solution1(root);
//        return solution2(root);
    }

    /**
     * dfs
     *
     * 最后判断 节点个数与节点序号是否相等
     *
     * @param root
     * @return
     */
    private boolean solution1(TreeNode root){
        // count-节点个数 seq-节点序号
        int count = postOrder(root, 1);

        return count==seq;
    }

    /**
     * 递归: 后序遍历
     *
     * 完全二叉树
     * 如果当前节点索引是idx(索引从1开始), 那么他的左右子节点索引为:
     * left = 2*idx
     * right = 2*idx+1
     *
     * @param root
     * @param idx
     * @return
     */
    private int postOrder(TreeNode root, int idx){
        if(root == null){
            return 0;
        }

        seq = Math.max(seq, idx);

        int leftCount = postOrder(root.left, 2*idx);
        int rightCount = postOrder(root.right, 2*idx+1);

        return leftCount+rightCount+1;
    }

    /**
     * bfs
     * @param root
     * @return
     */
    private boolean solution2(TreeNode root){
        return levelOrder(root);
    }

    /**
     * 层序遍历: 队列
     * 完全二叉树在遇到空节点之后剩余的应当全是空节点
     * @param root
     * @return
     */
    private boolean levelOrder(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        TreeNode node;
        while(queue.peek() != null){
            node = queue.poll();
            queue.offer(node.left);
            queue.offer(node.right);
        }

        // 剩余的应当全是空节点
        while(!queue.isEmpty() && queue.peek()==null){
            queue.poll();
        }

        return queue.isEmpty();
    }

    private class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }
}